﻿#pragma once
#include "stdafx.h"

/*
题目：下一个排列  中等
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

 

 示例 1：

 输入：nums = [1,2,3]
 输出：[1,3,2]
 示例 2：

 输入：nums = [3,2,1]
 输出：[1,2,3]
 示例 3：

 输入：nums = [1,1,5]
 输出：[1,5,1]
 示例 4：

 输入：nums = [1]
 输出：[1]

 解题思路，一个数的大小变换，举个例子，123456  下个数就是 123465，也就是要从后往前看下去。比如在下一个数，为
 123546.可以发现先4与5交换位置后，后面的要逆序下，当为654321的时候，就发现只要逆序下就好。所以只要知道规律后
 就非常的简单了
*/

void nextPermutation(vector<int>& nums) {
	if (nums.size()==0 || nums.size()==1)
	{
		return;
	}

	int i = nums.size() - 2;//下标
	int j = nums.size() - 1;//下标
	while (i>=0 && nums[i] >= nums[i+1])
	{
		i--;
	}
	if (i>=0)
	{		
		while (j>=0 && nums[i] >= nums[j])
		{
			j--;
		}
		swap(nums[i],nums[j]);
	}
	reverse(nums.begin()+i+1,nums.end());
}